主要是將陣列一分為二區分成左右陣列,直到只有一個元素才停止,接著逐一將左右陣列的第一個值互相比大小,小的值放到新陣列再把大的值放在它的後面,新的陣列完成後再跟上一層未做排序合併的陣列跑一次剛剛的動作,就這樣從分割到合併就形成這套演算法。
請執行這段程式並看程式中的log,log中的變化與影片中人物的移動是一樣的,希望可以幫助到大家,程式碼如下:
// Split the array into halves and merge them recursively
function mergeSort (arr) {
// return once we hit an array with a single item
if (arr.length === 1) {
return arr
}
const middle = Math.floor(arr.length / 2)
const leftArr = arr.slice(0, middle)
const rightArr = arr.slice(middle)
console.log('leftArr',leftArr);
console.log('rightArr',rightArr);
return merge(mergeSort(leftArr),mergeSort(rightArr))
}
// compare the arrays item by item and return the concatenated sortedArr
function merge (leftArr, rightArr) {
const sortedArr = [];
while (leftArr.length && rightArr.length) {
console.log(`${leftArr[0]} compare with ${rightArr[0]}`)
if (leftArr[0] < rightArr[0]) {
sortedArr.push(leftArr.shift())
} else {
sortedArr.push(rightArr.shift())
}
}
console.log('**sortedArr**',[...sortedArr,...leftArr,...rightArr]);
return [...sortedArr,...leftArr,...rightArr];
}
const arr=[4,2,8,6,0,5,1,7,3,9];
console.log(mergeSort(arr));